package array.others;

import java.util.Arrays;

/**
 * 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 * <p>
 * 示例 1：
 * <p>
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * <p>
 * 输出： True
 * <p>
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 * <p>
 * 示例 2:
 * <p>
 * 输入: nums = [1,2,3,4], k = 3
 * <p>
 * 输出: false
 * <p>
 * 来源：力扣（LeetCode）
 * <p>
 * 链接：<a href="https://leetcode.cn/problems/partition-to-k-equal-sum-subsets">698. 划分为k个相等的子集</a>
 */
public class N698_PartitionToKEqualSumSubsets {
    private int[] nums;
    private int[] cur;
    private int s;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        for (int num : nums)
            s += num;
        if (s % k != 0) return false;
        s /= k;
        Arrays.sort(nums);
        this.nums = nums;
        cur = new int[k];


        return dfs(nums.length - 1);
    }

    private boolean dfs(int i) {
        if (i < 0) return true;
        for (int j = 0; j < cur.length; ++j) {
            if (j > 0 && cur[j] == cur[j - 1]) continue;
            cur[j] += nums[i];
            if (cur[j] <= s && dfs(i - 1)) return true;
            cur[j] -= nums[i];
        }
        return false;
    }
}
